package com.demo.algorithms;

/**
 * 度量一个程序(算法)执行时间的两种方法：1.事后统计的方法 2.事前估算的方法
 * <p>
 * 时间复杂度
 * 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，
 * 用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，
 * T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。
 * 记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) )  为算法的渐进时间复杂度，简称时间复杂度
 * <p>
 * 时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，
 * 哪个算法中语句执行次数多，它花费时间就多。
 * 一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
 * <p>
 * 常见的时间复杂度：
 * 1.常数阶O(1)
 * 2.对数阶O(log2^n)
 * 3.线性阶O(n)
 * 4.线性对数阶O(nlog2^n)
 * 5.平方阶O(n^2)
 * 6.立方阶O(n^3)
 * 7.k次方阶O(n^k)
 * 8.指数阶O(2^n)
 * <p>
 * 常见的算法时间复杂度由小到大依次为：
 * Ο(1)＜Ο(log2^n)＜Ο(n)＜Ο(nlog2^n)＜Ο(n^2)＜Ο(n^3)＜ Ο(n^k) ＜Ο(2^n) ，
 * 随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
 * <p>
 * 计算时间复杂度方法：
 * 用常数1代替运行时间中的所有加法常数  T(n)=n²+7n+6  => T(n)=n²+7n+1
 * 修改后的运行次数函数中，只保留最高阶项  T(n)=n²+7n+1 => T(n) = n²
 * 去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)
 *
 * @author: 蔡奇峰
 * @date: 2020/7/13 22:52
 **/
public class TimeComplexity {

    /**
     * 1.常数阶O(1)
     * <p>
     * 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)
     */
    public static void constant() {
        int i = 1;
        int j = 7;
        j++;
        ++i;
        int sum = i + j;
    }

    /**
     * 2.对数阶O(log2^n)
     * <p>
     * 在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了
     */
    public static void logarithmic() {
        int n = 10;
        int i = 1;
        while (i < n) {

            i = i * 2;
        }
    }

    /**
     * 3.线性阶O(n)
     * <p>
     * for循环里面的代码会执行n遍，它消耗的时间是随着n的变化而变化的，
     * 因此这类代码都可以用O(n)来表示它的时间复杂度
     */
    public static void linearly() {
        int n = 100;
        int j = 0;
        for (int i = 1; i <= n; i++) {
            j = i;
            j++;
        }
    }

    /**
     * 4.线性对数阶
     * <p>
     * 将时间复杂度为O(logn)的代码循环N遍的话，
     * 那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)
     */
    public static void linearlyLogarithmic() {

        int n = 10;
        for (int i = 0; i < n; i++) {
            int j = 1;
            while (j < n) {

                j = j * 2;
            }
        }
    }

    /**
     * 5.平方阶O(n²)
     * <p>
     * 把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)，
     * 这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，
     * 即  O(n²) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(m*n)
     */
    public static void square() {
        int n = 10;
        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {
                j = i + j;
            }
        }
    }

    /**
     * 6.立方阶O(n³)、K次方阶O(n^k)
     * <p>
     * 代码其实就是嵌套了3层n循环，它的时间复杂度就是 O(n*n * n)，
     * 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(m*n)
     */
    public static void cube() {
        int n = 10;
        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                for (int k = 0; k < n; k++) {

                    k = i + j + k;
                }
            }
        }
    }

}


